/*
 * 4.1
 * Implement a function to check if a tree is balanced. For the purposes of this question,
 * a balanced tree is defined to be a tree such that no two leaf nodes differ in distance
 * from the root by more than one.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _tree_t {
    int value;
    struct _tree_t *left;
    struct _tree_t *right;
} tree_t;

/* return height, or -1 is not balanced. */
int height(tree_t *root)
{
    if (!root) {
        return 0;
    }
    int l = height(root->left);
    if (l == -1) {
        return -1;
    }
    int r = height(root->right);
    if (r == -1) {
        return -1;
    }
    int diff = l - r;
    if (diff >= -1 && diff <= 1) {
        return 1 + (l > r ? l : r);
    }
    return -1;
}

bool balance(tree_t *root)
{
    return height(root) != -1;
}

tree_t *new_tree(int v)
{
    tree_t *t = (tree_t *)malloc(sizeof(tree_t));
    memset(t, 0, sizeof(tree_t));
    t->value = v;
    return t;
}

void free_tree(tree_t *root)
{
    if (!root) {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main()
{
    tree_t *nodes[7];
    for (int i = 0; i < 7; i++) {
        nodes[i] = new_tree(i);
    }
    tree_t *root = nodes[0];
    root->left = nodes[1];
    nodes[1]->left = nodes[3];
    bool b = balance(root);
    printf("balance? %d\n", b);
    root->right = nodes[2];
    b = balance(root);
    printf("balance? %d\n", b);
    nodes[1]->right = nodes[4];
    nodes[4]->left = nodes[5];
    nodes[4]->right = nodes[6];
    b = balance(root);
    printf("balance? %d\n", b);
    free_tree(root);
    return 0;
}
